package structure;
import java.util.*;

public class Main61 {
    //
    
    //力扣232.用栈实现队列
    class MyQueue {
        Stack<Integer> stack1;
        Stack<Integer> stack2;
        public MyQueue() {
            stack1 = new Stack<Integer>();
            stack2 = new Stack<Integer>();
        }

        public void push(int x) {
            stack1.push(x);
        }

        public int pop() {
            if(!stack2.isEmpty()){
                return stack2.pop();
            }
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }

        public int peek() {
            if(!stack2.isEmpty()){
                return stack2.peek();
            }
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.peek();
        }

        public boolean empty() {
            return (stack1.isEmpty() && stack2.isEmpty());
        }
    }


    //力扣148. 验证图书取出顺序
    public static boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int len = pushV.length;
        int n = 0;
        //1 2 3 4 5
        //4 5 3 2 1
        for(int i = 0;i < len;++i) {
            if(n < len && (stack.isEmpty() || popV[n] != stack.peek())){
                stack.push(pushV[i]);
            }
            while ((!stack.isEmpty()) && stack.peek() == popV[n] ){
                stack.pop();
                n++;
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
    public static void main(String[] args) {
        int[] arr1 = {1,2,3,4,5};
        int[] arr2 = {4,5,3,2,1};
        System.out.println(IsPopOrder(arr1,arr2));
    }
}
